;; https://projecteuler.net/problem=32


;; Pandigital products
;; Problem 32

;; We shall say that an n-digit number is pandigital if it
;; makes use of all the digits 1 to n exactly once; for
;; example, the 5-digit number, 15234, is 1 through 5
;; pandigital.

;; The product 7254 is unusual, as the identity, 39 × 186 =
;; 7254, containing multiplicand, multiplier, and product is
;; 1 through 9 pandigital.

;; Find the sum of all products whose
;; multiplicand/multiplier/product identity can be written
;; as a 1 through 9 pandigital.

;; HINT: Some products can be obtained in more than one way
;; so be sure to only include it once in your sum.


(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ)
 (srfi srfi-69)  ; hash tables
 (srfi srfi-1)  ; reduce
 (contract)
 (lib math)
 (lib print-utils))


(define-with-contract pandigital?
  (require (natural-number? multiplicant)
           (natural-number? multiplier)
           (natural-number? product))
  (ensure (boolean? <?>))
  (λ (multiplicant multiplier product)
    (let ([number-digits
           (append (digits multiplicant)
                   (digits multiplier)
                   (digits product))])
      (and
       ;; Each digits from 1 to 9 must be contained exactly
       ;; once. If the numbers are 9 digits long in total,
       ;; and each of the digits from 1 to 9 is contained,
       ;; then each digit must be once in exactly one of the
       ;; numbers.
       ;; Check the length of the numbers in total.
       (= (+ (length (digits multiplicant))
             (length (digits multiplier))
             (length (digits product)))
          9)
       ;; Check, if every digit from 1 to 9 is contained.
       (reduce (λ (cur acc)
                 (and acc cur))
               #t
               (map (λ (digit)
                      ;; memv returns list instead of boolean
                      (pair? (memv digit number-digits))x)
                    (drop +decimal-digits+ 1)))))))


;; The multiplied numbers and their product must be 9 digits
;; long. All combinations, which result in less or more than
;; 9 digits length can be discarded.

;; If the multiplicant is longer, the multiplier will need
;; to be shorter and vice versa.

;; 1 cannot be a factor, because it would result in
;; duplicate digits in the resulting product.

;; The factors can at most have the following lengths,
;; otherwise they result in too long products:

;; 2 3 -> 4 (for example 99 * 100 = 9900, but +100 would be too long)

;; If the multiplicant is only 1 digit long, the multiplier
;; is at most 4999, (for multiplicant 2) otherwise there are
;; too many digits. The multiplier must be at least 4 digits
;; long to result in a product of another 4 digits and give
;; 9 digits in total.

;; If the multiplicant is 2 digits long, the multiplier can
;; at most be 999. That is the case for a multiplicant of 10
;; which is the lowest 2 digit number. -> Need to cover a
;; range from 10 to 99 and 100 to 999.

;; If the multiplicant is 3 digits long, this is the reverse
;; case of a multiplier being 3 digits long.

;; It seems the sum of digits in multiplicant and multiplier
;; is always 5. Maybe that is a useful fact for writing the
;; code?

;; Define some limits.
(define smallest-1digit-num 2)
(define smallest-2digit-num 10)
(define smallest-3digit-num 100)
(define smallest-4digit-num 1000)
(define biggest-1digit-num 9)
(define biggest-2digit-num 99)
(define biggest-3digit-num 999)
(define biggest-4digit-num 4999)


(let ([pandigital-combinations (make-hash-table equal?)])
  (let iter-for-len-1 ([multiplicant smallest-1digit-num]
                       [multiplier smallest-4digit-num])
    (let ([product (* multiplicant multiplier)])
      ;; Using `when` for side-effect of modifying the
      ;; hash-table and printing.
      (when (pandigital? multiplicant multiplier product)
        (print "found a pandigital at:" multiplicant multiplier product)
        (hash-table-set! pandigital-combinations
                         product
                         (cons multiplicant multiplier)))
      (cond
       [(> multiplier biggest-4digit-num)
        (print "multiplicant length 1: done")]
       [(> multiplicant biggest-1digit-num)
        (iter-for-len-1 2 (+ multiplier 1))]
       [else
        (iter-for-len-1 (+ multiplicant 1)
                        multiplier)])))

  (let iter-for-len-2 ([multiplicant smallest-2digit-num]
                       [multiplier smallest-3digit-num])
    (let ([product (* multiplicant multiplier)])
      (when (pandigital? multiplicant multiplier product)
        (print "found a pandigital at:" multiplicant multiplier product)
        (hash-table-set! pandigital-combinations
                         product
                         (cons multiplicant multiplier)))
      (cond
       [(> multiplier biggest-3digit-num)
        (print "multiplicant length 2: done")]
       [(> multiplicant biggest-2digit-num)
        (iter-for-len-2 2 (+ multiplier 1))]
       [else
        (iter-for-len-2 (+ multiplicant 1)
                        multiplier)])))

  ;; Now use the found results.
  (sum (hash-table-keys pandigital-combinations)))
